#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define ep emplace
#define pii pair<int,int>
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mems(arr,x) memset(arr,x,sizeof(arr))
#define memc(arr1,arr2) memcpy(arr1,arr2,sizeof(arr2))
using namespace std;
const int maxn=2010;
int n,m;
namespace Graph{
    vector<int> son[maxn];
    inline void add(int u,int v){son[u].eb(v);}
    inline void adde(int u,int v){add(u,v);add(v,u);}
    inline void rebuild(){for(int i=1;i<=n;i++)son[i].clear();}
    pii E[maxn];
}
using namespace Graph;
int mp[maxn][maxn];
int dp[maxn][maxn];
inline void getmn(int &x,int y){(x>y)&&(x=y);}
ll ans1=-2e18,ans2;
void check(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(mp[i][j])    dp[i][j]=1;
            else if(i==j)   dp[i][j]=0;
            else    dp[i][j]=1e9;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)   getmn(dp[j][k],dp[j][i]+dp[i][k]);
    ll sum=0;
    for(int i=1;i<=m;i++){
        auto [u,v]=E[i];
        sum-=dp[u][v];
    }
    if(sum>ans1)    ans1=sum,ans2=1;
    else if(sum==ans1)  ans2++;
}
void dfs(int u,int x,int s){
    if(s==m-1)  return check();
    if(u>n) return;
    dfs(u+1,0,s);
    for(int i=x;i<son[u].size();i++){
        mp[u][son[u][i]]=mp[son[u][i]][u]=true;
        dfs(u,x+1,s+1);
        mp[u][son[u][i]]=mp[son[u][i]][u]=false;
    }
}
void matt(){
    ans1=-2e18;
    rebuild();
    scanf("%d%d",&n,&m);
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        E[i]=pii(u,v);
        add(u,v);
    }
    dfs(1,0,0);
    printf("%lld %lld\n",ans1,ans2);
}
int main(){freopen("oi.in","r",stdin);freopen("oi.out","w",stdout);;int T;scanf("%*d%d",&T);while(T--)matt();}